package com.example.graph;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给定一个包含了一些 0 和 1 的非空二维数组 grid 。
 * 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
 * 你可以假设 grid 的四个边缘都被0（代表水）包围着。
 * 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
 * <p>
 * 示例 1:
 * <p>
 * {{0,0,1,0,0,0,0,1,0,0,0,0,0},
 * {0,0,0,0,0,0,0,1,1,1,0,0,0},
 * {0,1,1,0,1,0,0,0,0,0,0,0,0},
 * {0,1,0,0,1,1,0,0,1,0,1,0,0},
 * {0,1,0,0,1,1,0,0,1,1,1,0,0},
 * {0,0,0,0,0,0,0,0,0,0,1,0,0},
 * {0,0,0,0,0,0,0,1,1,1,0,0,0},
 * {0,0,0,0,0,0,0,1,1,0,0,0,0}}
 * <p>
 * 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
 * <p>
 * 示例 2:
 * <p>
 * {{0,0,0,0,0,0,0,0}}
 * <p>
 * 对于上面这个给定的矩阵, 返回 0。
 * <p>
 * 注意: 给定的矩阵grid 的长度和宽度都不超过 50。
 */
public class Leetcode695_MaxAreaOfIsland {
    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};

        System.out.println(new Solution().maxAreaOfIsland(grid));

    }

    private static class Solution {
        private int[][] directs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};// 定义上下左右四个方向
        private int areaSize;

        public int maxAreaOfIsland(int[][] grid) {
//            return maxAreaOfIsland1(grid);
            return maxAreaOfIsland2(grid);
        }

        /**
         * 解法一:Flood fill
         * <p>
         * 遍历整个网格,当发现'1'时将其"同化"为'0'或者其他数字都可以(目的是避免重复访问该元素)
         * BFS/DFS搜索四个方向发现'1'也要进行"同化",并记录该区域的面积
         *
         * @param grid
         * @return
         */
        public int maxAreaOfIsland1(int[][] grid) {
            int res = 0;
            if (grid == null || grid.length == 0 || grid[0].length == 0)
                return res;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        areaSize = 0;
                        dfs(grid, i, j);
                        res = Math.max(areaSize, res);
                    }
                }
            }
            return res;

        }

        /**
         * 解法二:并查集
         * @param grid
         * @return
         */
        public int maxAreaOfIsland2(int[][] grid) {
            int res = 0;
            if (grid == null || grid.length == 0 || grid[0].length == 0)
                return res;
            UnionFindSet uf = new UnionFindSet(grid);
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        int set1 = uf.hash(i, j, grid[0].length);

                        for (int[] direct : directs) {
                            int newX = i + direct[0];
                            int newY = j + direct[1];
                            if (newX >= 0 && newX < grid.length &&
                                    newY >= 0 && newY < grid[0].length &&
                                    grid[newX][newY] == 1) {
                                int set2 = uf.hash(newX, newY, grid[0].length);
                                uf.union(set1, set2);
                            }
                        }
                    }
                }
            }

            int[] size = uf.getSize();
            Arrays.sort(size);

            return size[size.length - 1];

        }

        private void dfs(int[][] grid, int x, int y) {
            if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0)
                return;
            grid[x][y] = 0;
            areaSize++;
            for (int[] direct : directs) {
                dfs(grid, x + direct[0], y + direct[1]);
            }
        }

        private class UnionFindSet {
            private int[] parent;// 每个节点的父节点
            private int[] rank; // 每个集合的秩
            private int[] size;// 每个集合的元素个数()

            public UnionFindSet(int[][] grid) {
                int rows = grid.length;
                int columns = grid[0].length;
                parent = new int[rows * columns];
                size = new int[rows * columns];
                rank = new int[rows * columns];
                for (int x = 0; x < rows; x++) {
                    for (int y = 0; y < columns; y++) {
                        if (grid[x][y] == 1) {
                            int v = hash(x, y, columns);
                            parent[v] = v;
                            size[v] = 1;
                            rank[v] = 1;
                        }
                    }
                }
            }

            public int find(int node) {
                if (parent[node] != node) {
                    // 递归地查找父节点的父节点，并将其作为当前节点的父节点(完成了路径压缩)
                    parent[node] = find(parent[node]);
                }
                return parent[node];
            }

            public void union(int set1, int set2) {
                int root1 = find(set1);
                int root2 = find(set2);

                if (root1 != root2) { // 两个集合的代表代表元(根节点)不同才进行合并
                    System.out.println("合并");
                    // 按秩合并
                    if (rank[root1] > rank[root2]) {
                        parent[root2] = root1;
                        size[root1] += size[root2];
                        size[root2] = 0;
                    } else if (rank[root1] < rank[root2]) {
                        parent[root1] = root2;
                        size[root2] += size[root1];
                        size[root1] = 0;
                    } else {
                        parent[root2] = root1;
                        rank[root1] += 1;
                        size[root1] += size[root2];
                        size[root2] = 0;
                    }
                }

            }

            public int[] getSize() {
                return size;
            }

            public int hash(int i, int j, int constant) {
                return i * constant + j;
            }
        }
    }
}
